import java.text.DecimalFormat;
import java.text.NumberFormat;
import java.util.HashSet;
import java.util.Random;

public class Apl {
	public static void main(String[] args) {
		new Apl();
	}
	
	private NumberFormat formatter = new DecimalFormat("#0.00000");
	
	public Apl() {
//		int[] algoritme1Numbers = { 5000, 10000, 20000, 50000, 100000 };
//		for(int i = 0; i < algoritme1Numbers.length; i++) {
//			System.out.println("Algoritme 1 met "+ algoritme1Numbers[i] +" nummers.");
//			algoritme1(algoritme1Numbers[i]);
//			System.out.println("+++++++++++++++++++++++++++++++++");
//		}
//
//		int[] algoritme2Numbers = { 100000, 500000, 1000000, 5000000, 10000000 };
//		for(int i = 0; i < algoritme2Numbers.length; i++) {
//			System.out.println("Algoritme 2 met "+ algoritme2Numbers[i] +" nummers.");
//			algoritme2(algoritme2Numbers[i]);
//			System.out.println("+++++++++++++++++++++++++++++++++");
//		}
		
		int[] algoritme3Numbers = { 5000000, 10000000, 20000000, 40000000, 80000000 };
		for(int i = 0; i < algoritme3Numbers.length; i++) {
			System.out.println("Algoritme 3 met "+ algoritme3Numbers[i] +" nummers.");
			algoritme3(algoritme3Numbers[i]);
			System.out.println("+++++++++++++++++++++++++++++++++");
		}
	}
	
	// Vul een array a van a[0] tot a[N-1] als volgt: om a[i] te vullen, genereer je net zo lang
	// een random getal totdat er een is gevonden die niet gelijk is aan a[0] t/m a[i-1].
	private void algoritme1(int n) {
		int[] elements = new int[n];

		long totalRunningTime = 0;
		for(int x = 0; x < 10; x++) {
			long startTime = System.currentTimeMillis();
			
			Random random = new Random();
			elements[0] = random.nextInt(n);
			
			for(int i = 1; i < n; i++) {
				int number = random.nextInt(n);
				
				int j = 0;
				boolean foundNumber = false;
				while(j < i) {
					if(elements[j] == number) {
						foundNumber = true;
						break;
					}	
					j++;
				}
				
				if(foundNumber) {
					i--;
				} else {
					elements[i] = number;
				}
			}
			
			long endTime = System.currentTimeMillis();
			totalRunningTime += (endTime - startTime);
			
			//System.out.println("Execution time is "+ formatter.format((endTime - startTime) / 1000d) +" seconds.");
		}
		
		System.out.println("Avarage time is "+ formatter.format((totalRunningTime / 10) / 1000d) +" seconds.");
	}
	
	// Analoog aan algoritme 1, maar hou nu een extra array used bij. Wanneer een random
	// getal r in array a wordt gezet, zet dan ook used[r] op true. Bij het vullen van a[i]
	// kunnen we nu dus direct zien of het gegenereerde random getal al gebruikt is of niet
	// (i.p.v. alle plaatsen a[0] t/m a[i-1] langs te lopen).
	private void algoritme2(int n) {
		int[] elements = new int[n];
		
		long totalRunningTime = 0;
		for(int x = 0; x < 10; x++) {
			boolean[] used = new boolean[n];
			
			long startTime = System.currentTimeMillis();
			
			Random random = new Random();
			elements[0] = random.nextInt(n);
			used[elements[0]] = true;
			
			for(int i = 1; i < n; i++) {
				int number = random.nextInt(n);
				
				if(used[number]) {
					i--;
				} else {			
					elements[i] = number;
				}
				used[number] = true;
			}
			
			long endTime = System.currentTimeMillis();
			totalRunningTime += (endTime - startTime);
			
			//System.out.println("Execution time is "+ formatter.format((endTime - startTime) / 1000d) +" seconds.");
		}
		
		System.out.println("Avarage time is "+ formatter.format((totalRunningTime / 10) / 1000d) +" seconds.");
	}

	// Vul het array zodat a[i] = i. Verwissel vervolgens de inhoud van a[i] met een
	// willekeurige andere positie in de array, dus swap(a[i], a[randInt(0,i)]).
	private void algoritme3(int n) {
		int[] elements = new int[n];
		
		long totalRunningTime = 0;
		for(int x = 0; x < 10; x++) {
			long startTime = System.currentTimeMillis();
			
			Random random = new Random();
			
			for(int i = 0; i < n; i++) {
				int number = random.nextInt(n);
				elements[i] = number;
			}
			
			for(int i = 0; i < n; i++) {
				// Swap
				int newRandomPosition = random.nextInt(n);
				int tmp = elements[i];
				elements[i] = elements[newRandomPosition];
				elements[newRandomPosition] = tmp;
			}
			
			long endTime = System.currentTimeMillis();
			totalRunningTime += (endTime - startTime);
			
			//System.out.println("Execution time is "+ formatter.format((endTime - startTime) / 1000d) +" seconds.");
		}
		
		System.out.println("Avarage time is "+ formatter.format((totalRunningTime / 10) / 1000d) +" seconds.");
	}
	
	private void printArray(int[] array) {
		for(int i = 0; i < array.length; i++) {
			System.out.println(array[i]);
		}
	}
	
	public boolean hasDuplicates(int[] array) {
		HashSet<Integer> set = new HashSet<Integer>();
		for(int i = 0; i < array.length; i++) {
			if(set.contains(array[i])) {
				return true;
			} else {
				set.add(array[i]);
			}
		}
		return false;
	}
}
